The present invention relates to a viterbi decoder employed for maximum likelihood decoding of convolutional codes.
Multipath phasing occurring in radio communication such as mobile communications and satellite communications caused by obstructions such as buildings results in a different code sequence received at the reception side from the code sequence transmitted by the transmission side. If such an error in code transmission occurs in, for instance, voice encoding, the quality of reproduced sound at the reception side will be greatly degraded, necessitating appropriate error correction.
Convolutional codes, which can be decoded to achieve a result that is the maximum likelihood or close to the maximum likelihood through viterbi decoding, are effective codes for use in a communication path such as a radio line, in which the error rate in transmitted code is high. FIG. 17 presents an example of an encoder that performs convolutional encoding at an encoding rate R=1/2 with a constraint length of K=3.
In this convolutional encoder 101, three bits including the most recent one bit input are stored at a buffer 103 and through convolutional encoding, an output of two bits is achieved. One of the two bits thus output represents the results of calculation performed by an exclusive OR gate (not shown) on all the bits in the buffer 103, whereas the other one bit indicates the results of calculation performed by another exclusive OR gate (not shown) on the first and third bits in the buffer 103.
FIG. 18 presents a trellis chart achieved by rendering the generating conventions of convolutional encoding performed by the convolutional encoder 101 into a state transition diagram. In this trellis chart 111, time points "t" corresponding to instances of convolutional encoding are indicated in the horizontal direction and the states of the encode word are indicated in the vertical direction. In addition, the number of states, which is determined by the constraint length K=m+1, is expressed as 2.sup.m. Consequently, the number of states in this diagram is 4, which corresponds to states S0-S3, as shown in FIG. 18.
In viterbi decoding, maximum likelihood decoding is performed by determining the metric for each of the states S0-S3 at the individual time points "t" in the trellis chart 111, and this decoding may be realized by employing a viterbi decoder 121 illustrated in FIG. 19.
The following is an explanation of the operation of the viterbi decoder 121. First, a reception sequence Y is input to a branch metric calculating unit (hereafter referred to as a "BMG") 123. As shown in the trellis chart 111, there are two paths (hereafter referred to as "branches") through which input is performed for each of the states S0-S3, and the BMG 123 calculates metrics for all the branches. A path selection unit (hereafter referred to as an "ACS") 125 compares the sums of the accumulated totals (path metrics) of the branch metrics at the states S0-S3 at the time point t-1 immediately before the branches become linked and their branch metrics for two input branches for each of the states S0-S3 at a time point "t" and selects the one that is more likely, to assign it as a new path metric at each of the states S0-S3. Thus, for each branch that is to link with each of the states S0-S3, information on the path reaching each of the states S0-S3 is stored in a path memory unit (hereafter referred to as a"PMEM") 127 and a decode sequence W is output with specific timing.
Now, in order to achieve maximum likelihood decoding in the strict sense by employing the viterbi decoder 121, it is necessary that the viterbi decoding continue until the reception sequence Y is completed. However, since the reception sequence Y is normally quite long, a tremendous memory capacity is required in the PMEM 127 and an excessive length of time is required for the decoding.
It has been learned through experience that under normal circumstances, as long as an encode sequence length that is 5-6 times the constraint length K is assured, decoding that is extremely close to maximum likelihood decoding in the strictest sense is possible with a viterbi decoder. Based upon this finding, the truncation encode sequence length of the convolutional encoder 101 with a constraint length K=3, i.e., the number of truncations T, is set at T=18 in correspondence to the time points t=0-17, as illustrated in FIG. 18. The memory capacity of the PMEM 127 in the viterbi decoder 121 is determined in correspondence to the truncations T=18.
As illustrated in FIG. 20, the PMEM 127 in the prior art is constituted of unit path memories 131, the number of which that are be connected corresponds to the product of the number of states S0-S3 and the number of stages of the truncations T. In addition, the unit path memories 131 are each constituted of a selector 133 and a shift register 135, and store in memory the results of the selections of the maximum likelihood paths at states S0-S3 at the time points t=0-17.
Furthermore, the soft decision making system, in which the reception sequence Y is handled as input data having a bit-width of several bits, is often adopted in viterbi decoders in order to enhance their error correction capabilities. By adopting this method, since the input data are repeatedly added in correspondence to the encoding rate R during the branch metric calculation performed by the BMG 123, the bit-width of the data obtained as a result of the calculation increases in correspondence to the bit-width of the input data. Since the ACS125 repeats state metric calculation and state transition a plurality of times, based upon the data obtained through the branch metric calculation performed at the BMG 123, the calculation bit-width at the ACS 125 will exhibit some spreading.
Since the total ratio of the areas occupied by the BMG and the ACS in the entire viterbi decoder sometimes reaches 40% under specific conditions, reducing the ACS circuit scale will directly lead to a reduction in the scale of the viterbi decoder. Thus, in the prior art, the ACS is made to perform processing such as simultaneous subtraction of state metric values in order to avoid an overflow or an underflow in the calculation, to ensure that the circuit scale does not become excessively large.
Normally, an ACS is provided with ACS circuits that perform state metric calculation for the individual states, and the ACS 125 is provided with four ACS circuits 201, one of which is illustrated in FIG. 21. While the number of the adders, comparators, selectors and the like constituting each ACS circuit 201 increases in correspondence to the calculation bit-width explained above, the increase in the calculation bit-width does not result in a large increase in the circuit scale of the ACS 125 as long as the number of ACS circuits 201 is kept down to four or so. However, if the constraint length is increased from K=3 to K=9 in order to improve the error code capability, the number of ACS circuits 201 increases in an exponential function from 4 to 256, resulting in an increase in the scale of the ACS 125 and, ultimately, an increase in the scale of the entire viterbi decoder 121. In the prior art, this problem is handled by providing circuits 125 in a quantity representing 1/N of the number of states and by repeating the calculation of state metrics at the ACS circuits 125 N times, i. e., by performing the calculations using time sharing.